A graph isomorphism process is a procedure for determining whether one graph is equivalent or isomorphic to another; for example, whether there exists a bijective mapping from one graph to another. A subgraph isomorphism process is a procedure for determining whether one graph (e.g., a subgraph) is contained within another graph; for example, whether there exists a subset of the target graph that is isomorphic to the subgraph. In the latter case, the bijective mapping of the subgraph to the subset of the target graph is also an injective morphism from the subgraph to the target graph.
Existing applications of graph isomorphism processes and subgraph isomorphism processes seek principally to answer the question of equivalence by finding a bijective mapping from one graph to another graph or to some subset of another graph. If no mapping exists, then differences between the graphs may be presented such that modifications may be made to make such a mapping possible.
A conventional program using a graph isomorphism process is the Gemini program. (See e.g., C. Ebeling and O. Zajicek, “Validating VLSI Circuit Layout by Wirelist Comparison,” Proceedings of the Conference on Computer Aided Design (ICCAD), pp 172-173, 1983.) The Gemini program first models circuits as graphs having nodes (vertices). Devices (e.g., transistors) are represented as device nodes, and the interconnections (e.g., wires) are represented as net nodes. The net nodes link together the device nodes. An application of Gemini is to form one graph for a wirelist that is extracted from a layout and another graph from a specification wirelist. The Gemini program then runs a graph isomorphism process to compare the two graphs and reports if they are exactly the same. If they are not the same, the program may report differences between the underlying circuits. A typical use of this program is to determine whether a VLSI circuit layout is correct and to report differences as errors.
Another conventional program seeks to find subcircuits in a larger circuit. For example, SubGemini is a program that uses a subgraph isomorphism process to find subcircuits in a larger circuit. (See e.g., M. Ohlrich, C. Ebeling, E. Ginting, and L. Sather, “SubGemini: Identifying SubCircuits Using a Fast Subgraph Isomorphism Algorithm”, Proceedings of the 30th ACM/IEEE Design Automation Conference, pp 31-37, 1993.) This may be useful to identify a related group of primitive resources that function as a higher level device. For example, a common problem that this conventional program seeks to solve is converting a transistor netlist into a gate netlist.
However, such conventional techniques using graph or subgraph isomorphism processes do not seek to determine if there are multiple ways in which the first circuit maps onto the second circuit. Thus, these conventional techniques are not designed to determine optimal solutions.
Furthermore, the target circuit to which the mapping is being done is considered to be static. For example, there is no provision for modifying the target circuit to accommodate the circuit that is being mapped to it. Thus, existing techniques do not provide a means to map to a programmable hardware resource space.